class Solution(object):
    def reverseList(self, head):
        pre = None
        cur = head
        while cur != None:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        #找到中间节点
        slow = head
        fast = head
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
        mid = slow
		#奇数个节点
        if fast is not None:
            mid = slow.next
        
        #reverse后半段
        right = self.reverseList(mid)
        while right != None:
            if head.val != right.val:
                return False
            head = head.next
            right = right.next
        return True
